package com.julius.design.suanfa.search;

/**
 * @author julius
 * @date 2021-10-22 上午 11:10
 * <p>
 *      查重复数字 (非严格有序数组的二分查找)
 *      https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
 * </p>
 */
public class SearchNumber {


    public static int search(int[] nums, int target) {
        /*
            1. 暴力循环  时间复杂度为 O(N) 所以不能使用
            2. 二分查找
            8
            5,7,7,8,8,8,8,10,10,11,12
            0 1 2 3 4 5 6 7  8  9  10
        */
        int leftIdx = binarySearch(nums,target,true);

        int rightIdx = binarySearch(nums,target,false)-1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return rightIdx - leftIdx + 1;
        }
        return 0;
    }

    public static int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,7,7,8,8,8,8,10,10,11,12};

        int target = 8;

        System.out.println(search(nums,target));
    }
}
